{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 第5章-决策树-导读\n",
    "&emsp;&emsp;本章书上的内容看起来很多，但其实决策树是一个比较简单，而且容易可视化的统计学习模型。决策树模型既可以用来做分类问题，也可以用来做回归问题，书中主要讲的是分类问题。本章 模型的特点是输出变量$Y$是一个分类变量，输入变量$X$主要也是分类变量。  \n",
    "### 决策树模型与学习\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/5-2-Sample-Data-Table.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">表5-1  贷款申请样本数据表</div></center>  \n",
    "\n",
    "&emsp;&emsp;该表一共有15条数据（实例），“类别”为输出变量$Y$，是一个二分类，分别对应“否”和“是”，“否”表示此人贷款申请失败（不被批准），“是”表示此人贷款申请成功（被批准），对于每一个示例，有4个输入变量，即$X$是4维的，年龄分为青年、中年、 老牛，有工作分为是和否，有自己的房子分为是和否，信贷情况分为一般、好、非常好。\n",
    "<br/><center>\n",
    "<img style=\"border-radius: 0.3125em;box-shadow: 0 2px 4px 0 rgba(34,36,38,.12),0 2px 10px 0 rgba(34,36,38,.08);\" src=\"../../../PhaseFour/Note/image/5-1-Decision-Tree-Generation.png\"><br><div style=\"color:orange; border-bottom: 1px solid #d9d9d9;display: inline-block;color: #000;padding: 2px;\">图5-1  决策树生成</div></center>  \n",
    "\n",
    "&emsp;&emsp;决策树模型最后要得到的为上面这个图，根据上图，任意用一个实例，可以判定数据的预测类别。图中有以下几个术语：  \n",
    "- 根结点：图中“有自己的房子”这个结点为根结点。\n",
    "- 内部结点：图中“有工作”这个结点为内部结点。\n",
    "- 叶子结点：图中“是”和“否”的方形结点为叶子结点。\n",
    "\n",
    "&emsp;&emsp;根据训练集中的输入变量，首先找到一个根结点，通过根结点判断所属类别，分成不同的分支，在分支下面继续寻找下一个用来分类的输入变量（即内部结点），以上是决策树模型类别判定过程描述。  \n",
    "&emsp;&emsp;虽然决策树模型有非常好的可视化性质，但是也有一些问题，需要通过哪些准则来寻找根结点？当寻找根结点时，直观上说，要一个分类效果最好，可以通过特征选择。树状结构停止的标准是什么？其实并不需要将训练实例中所有的特征都放在决策树中，假设有非常多的特征，如果将它们都放入决策树中，决策树中对应的每一个叶子结点会对应于训练集中的每一个实例，也就是说，该决策树在训练集上表现很好，很容易过拟合。  \n",
    "&emsp;&emsp;决策树中比较重要的两个问题：第一个是如何选择分类的特征，第二个是如何避免过拟合。  \n",
    "\n",
    "### 特征选择\n",
    "#### 熵\n",
    "熵：$\\displaystyle H(X)=-\\sum_{i=1}^{n} p_{i} \\log p_{i}$  \n",
    "&emsp;&emsp;在本章中，讨论的都是离散型的随机变量（即可分类的），对于分类变量，假如有$n$个不同的类别，每一个类别出现的概率是$p_i$，熵为$\\displaystyle H(X)=-\\sum_{i=1}^{n} p_{i} \\log p_{i}$。其中$\\log$是以2为底的对数，熵衡量的是随机变量的混乱程度。  \n",
    "&emsp;&emsp;现根据前面的例子，可以看到有15个人的数据，在最终的分类变量$Y$上的离散程度。观察类别：一共出现了6个“否”，9个“是”；由于$p_i$是由样本求出的，H(X)也称为经验熵。  \n",
    "15个实例在$Y$上面的经验熵为：$\\displaystyle -\\left(\\frac{6}{15} \\log \\frac{6}{15}+\\frac{9}{15} \\log \\frac{9}{15}\\right)$  \n",
    "&emsp;&emsp;现选择一个特征，将数据分组，希望的目标是按照此特征，分组出来的数据全部都是“是”，另一组全部都是“否”，计算两个分组的经验熵：$-1\\log 1 =0$，两组的经验熵都是0。但是很难选择一个特征，将两类数据完全分开，这样就需要对比每一个特征对样本数据的混乱程度（熵）。  \n",
    "&emsp;&emsp;以下用一个特征举例，比如“有工作”这个特征，按照这个特征将数据集分成两个部分，有工作的有5人，最后申请贷款成功的有5人，没有工作的有10人，最后申请贷款成功的有4人，申请贷款失败的有6人。条件熵为$\\displaystyle \\frac{5}{10} \\times -1\\log1 +\\frac{10}{15} \\times\\left(-( \\frac{6}{10} \\log \\frac{6}{10}+\\frac{4}{10} \\log \\frac{4}{10})\\right)$  \n",
    "\n",
    "#### 信息增益\n",
    "信息增益：$g(D, A)=H(D)-H(D|A)$  \n",
    "&emsp;&emsp;给定$A$的条件下$D$的熵$H(D|A)$，之前没有对数据进行分类，经验熵为$H(D)$，现在根据“有工作”这个特征将数据分类，在这一过程中，数据混乱的减少程度，叫做信息增益。  \n",
    "&emsp;&emsp;当选择第一个根结点时，在所有的特征中，寻找一个信息增益最大的特征，作为根结点，一步一步地从剩下的特征中选择信息增益最大的，作为下一个内部结点。虽然该特征选择方法比较好理解，但是有一个缺点，如果有一个特征A，其类别非常多，现有15个数据实例，特征A有15个不同的类别，导致会有15个分支，对应结点的熵为0，条件熵为0，信息增益会很大，很容易出现过拟合。针对这个情况，对信息增益做了改进，采用信息增益比来选择特征。\n",
    "\n",
    "#### 信息增益比\n",
    "信息增益比：$\\displaystyle g_{R}(D, A)=\\frac{g(D,A)}{H_{A}(D)}$  \n",
    "&emsp;&emsp;根据上述公式，可以看到分子是信息增益，而分母是$H_A(D)$，考虑到了特征A本身的混乱程度（熵）。根据上一个例子，将样本数据按照“有工作”分成了两类，有工作为5个，没工作有10个，可得$\\displaystyle H_{A}(D)=-( \\frac{5}{15} \\log \\frac{5}{15}+\\frac{10}{15} \\log \\frac{10}{15} )$，类别分得越多，混乱程度越大（即熵值越大）。\n",
    "\n",
    "### 决策树的生成\n",
    "#### 算法5.2（ID3算法）  \n",
    "输入：训练数据集$D$，特征集$A$，阈值$\\varepsilon$    \n",
    "输出：决策树$T$  \n",
    "（1）若$D$中所有实例属于同一类$C_k$，则$T$为单结点树，并将类$C_k$作为该结点的类标记，返回$T$；    \n",
    "（2）若$A \\neq \\varnothing$，则$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的类标记，返回$T$；    \n",
    "（3）否则，按算法5.1计算$A$中各特征对$D$的**信息增益**，选择**信息增益**最大的特征$A$；    \n",
    "（4）如果$A_g$的信息增益小于阈值$\\varepsilon$，则置$T$为单结点树，并将$D$中实例数最大的类$C_g$作为该结点的类标记，返回$T$；  \n",
    "（5）否则，对$A_g$的每一个可能值$a_i$，依$A_g=a_i$将$D$分割为若干非空子集$D_i$，将$D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树$T$，返回$T$；  \n",
    "（6）对第$i$个子结点，以$D_i$为训练集，以$A-\\{A_g\\}$为特征集，递归地调用（1）~（5），得到子树$T_i$，返回$T_i$。  \n",
    "\n",
    "#### 算法5.2（C4.5算法） \n",
    "输入：训练数据集$D$，特征集$A$，阈值$\\varepsilon$    \n",
    "输出：决策树$T$  \n",
    "（1）若$D$中所有实例属于同一类$C_k$，则$T$为单结点树，并将类$C_k$作为该结点的类标记，返回$T$；    \n",
    "（2）若$A \\neq \\varnothing$，则$T$为单结点树，并将$D$中实例数最大的类$C_k$作为该结点的类标记，返回$T$；    \n",
    "（3）否则，按公式$\\displaystyle g_{R}(D, A)=\\frac{g(D,A)}{H_{A}(D)}$计算$A$中各特征对$D$的**信息增益比**，选择**信息增益比**最大的特征$A$；    \n",
    "（4）如果$A_g$的信息增益小于阈值$\\varepsilon$，则置$T$为单结点树，并将$D$中实例数最大的类$C_g$作为该结点的类标记，返回$T$；  \n",
    "（5）否则，对$A_g$的每一个可能值$a_i$，依$A_g=a_i$将$D$分割为若干非空子集$D_i$，将$D_i$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树$T$，返回$T$；  \n",
    "（6）对第$i$个子结点，以$D_i$为训练集，以$A-\\{A_g\\}$为特征集，递归地调用（1）~（5），得到子树$T_i$，返回$T_i$。  \n",
    " \n",
    "### 决策树的剪枝\n",
    "&emsp;&emsp;前面两个算法都通过限定阈值，避免生成的决策树很深，造成过拟合。这种方法叫做预剪枝，也就是说，在树的生成过程中，已经考虑了不生成很宽很深的树，有一些分支被剪掉了。书中5.4节，所讲的是后剪枝，当生成整个树之后，如何再砍掉一些分支，让决策树更精简，增强泛化能力。   \n",
    "&emsp;&emsp;决策树损失函数：$C_{\\alpha}(T)=C(T)+\\alpha|T|$，其中$C(T)=\\displaystyle \\sum_{t=1}^{|T|} N_t H_t(T)$  \n",
    "**说明：** $\\alpha$表示对树规模的一个惩罚；$|T|$表示这个决策树有多少个叶子结点，例如图5-1中，叶子结点有3个，当叶子结点数越大，说明决策树模型越复杂，其泛化能力差，$\\alpha|T|$表示模型的复杂度； $C(T)$表示模型对训练集数据的拟合程度，用熵来度量，当叶子结点上面的条件熵越小时，所对应的损失越小，熵越小，代表数据越整齐，混乱程度越低，当模型用于分类的时候，分类效果更好。  \n",
    "&emsp;&emsp;首先计算原始$C_\\alpha(T)$，再剪枝，计算剪枝之后的$C_\\alpha(T')$，如果$C_\\alpha(T') < C_\\alpha(T)$，则可以剪枝，如果$C_\\alpha(T') \\geqslant C_\\alpha(T)$，则不可以剪枝。  \n",
    "\n",
    "### CART算法\n",
    "&emsp;&emsp;这个算法对应的就是一个二叉树，上面两种算法（ID3和C4.5）可以按照类别个数进行分类，但是这个算法，不论特征有多少类别，都划分成两类。依然以之前的贷款申请为例，按照“年龄”，有“青年”、“中年”、“老年”，但按照该算法，可分为“青年”和“非青年”，或者为“中年”和“非中年”。那么要如何选择类别呢？提出了一个新的判别方法，称为基尼指数。  \n",
    "基尼指数：$\\displaystyle \\text{Gini}(p)=\\sum_{k=1}^K p_k(1-p_k)$  \n",
    "在特征$A$的条件下，集合$D$的基尼指数：$\\displaystyle \\text{Gini}(D, A)=\\frac{|D_1|}{|D|} \\text{Gini}(D_1)+\\frac{|D_2|}{|D|} \\text{Gini}(D_2)$  \n",
    "&emsp;&emsp;在CRAT算法中，选择$\\text{Gini}(D,A)$最小的特征来进行决策树的分支，这个时候就不用再考虑特征$A$对于集合$D$的混乱程度，因为在CRAT算法中，只划分两类，不会导致信息增益很大。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
